package prepare;

import java.util.*;


public class Test {
    public static void main(String[] args) {

        // int[] 1,2,3,6,7
        // 1, 6, 2, 4, 8, 3, 7
        // 1, 6,8 | 1, 2,4,8 | 1, 2, 3, 7 |
        // dp[i] 以 i 结尾的最大序列长度
        // dp[i ] = 1, dp[i - 1] + 1, 2.

    }

    public List<Integer> getMaxLength(int[] array) {
        if (array == null || array.length == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> batchList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int last = array[0];
        list.add(last);
        for (int i = 1; i < array.length; i++) {
            if (array[i] > last) {
                list.add(array[i]);
            } else {
                batchList.add(list);
                list = new ArrayList<>();
                list.add(array[i]);
            }
            last = array[i];
        }
        // 假设默认只有1个最大值
        Map<Integer, List<Integer>> lengthMap = new HashMap<>();
        int maxLength = 0;
        for (List<Integer> batch : batchList) {
            maxLength = Math.max(batch.size(), maxLength);
            lengthMap.put(batch.size(), batch);
        }
        return lengthMap.get(maxLength);
    }

    public int getMaxLengthWithDp(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int[] dp  = new int[array.length];

        dp[0] =1 ;
        for (int i = 1; i < array.length; i ++) {
            int maxLength = getMaxDpLength(i, dp, array);
            dp[i] = maxLength;
        }
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }
        return maxLength;
    }

    private int getMaxDpLength(int i, int[] dp, int[] array) {
        int index = i - 1;
        int maxLength = 0;
        while (index >= 1) {
            if (array[i] > array[index]) {
                maxLength = Math.max(maxLength, dp[index] + 1);
            }
        }
        return maxLength;
    }
}


